/*
 * @lc app=leetcode.cn id=1334 lang=csharp
 *
 * [1334] 阈值距离内邻居最少的城市
 */

// @lc code=start
public class Solution {
    public int FindTheCity(int n, int[][] edges, int distanceThreshold) {
        int index = 0;
        int[,] dp = new int[n,n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i,j] = int.MaxValue;
            }
        }
        for(int i = 0; i < edges.Length; i++){
            dp[edges[i][0],edges[i][1]] = edges[i][2];
            dp[edges[i][1],edges[i][0]] = edges[i][2];
        }
        for(int i = 0; i < n; i++){
            dp[i,i] = 0;
        }
        for(int k = 0; k < n; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    dp[i,j] = Math.Min(dp[i,j],dp[i,k] + dp[k,j]);
                }
            }
        }
        int min = int.MaxValue;
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = 0; j < n; j++){
                if(dp[i,j] <= distanceThreshold){
                    count++;
                }
            }
            if(count > 0 && count <= min){
                min = count;
                if(i > index){
                    index = i;
                }
            }
        }
        return index;
    }
}
// @lc code=end

